home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr31 / decomp2.zip / DECOMP.C next >
Text File  |  1993-05-12  |  10KB  |  376 lines
  1. /*
  2.  * Compress - data compression program
  3.  */
  4. #define    min(a,b)    ((a>b) ? b : a)
  5.  
  6. # define BITS   16
  7. #define HSIZE 1L<<BITS
  8. /*
  9.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  10.  */
  11. #if BITS > 15
  12. typedef long int    code_int;
  13. #else
  14. typedef int        code_int;
  15. #endif
  16.  
  17. #ifdef SIGNED_COMPARE_SLOW
  18. typedef unsigned long int count_int;
  19. typedef unsigned short int count_short;
  20. #else
  21. typedef long int      count_int;
  22. #endif
  23.  
  24. #ifdef NO_UCHAR
  25.  typedef char    char_type;
  26. #else
  27.  typedef    unsigned char    char_type;
  28. #endif /* UCHAR */
  29. char_type magic_header[] = { "\037\235" };    /* 1F 9D */
  30.  
  31. /* Defines for third byte of header */
  32. #define BIT_MASK    0x1f
  33. #define BLOCK_MASK    0x80
  34. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  35.    a fourth header byte (for expansion).
  36. */
  37. #define INIT_BITS 9            /* initial number of bits/code */
  38.  
  39. /*
  40.  * compress.c - File compression ala IEEE Computer, June 1984.
  41.  *
  42.  * Authors:    Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  43.  *        Jim McKie        (decvax!mcvax!jim)
  44.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  45.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  46.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  47.  *        Joe Orost        (decvax!vax135!petsd!joe)
  48.  *
  49.  * modified for MS-DOS, decompression only, by B.D. Ripley, 1/90
  50.  *        b.d.ripley@uk.ac.strath.vaxa
  51.  */
  52.  
  53. #include <stdio.h>
  54. #include <ctype.h>
  55. #include <alloc.h>
  56. #include <sys/types.h>
  57. #include <sys/stat.h>
  58.  
  59. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  60.  
  61. int n_bits;                /* number of bits/code */
  62. int maxbits = BITS;            /* user settable max # bits/code */
  63. code_int maxcode;            /* maximum code, given n_bits */
  64. code_int maxmaxcode = 1L << BITS;    /* should NEVER generate this code */
  65. # define MAXCODE(n_bits)    ((1L << (n_bits)) - 1)
  66.  
  67. char_type huge *htab;
  68. unsigned short huge *codetab;
  69. count_int fsize, hsize;
  70.  
  71. #define tab_prefixof(i)    codetab[i]
  72. #define tab_suffixof(i)    htab[i]
  73.  
  74. char_type *de_stack;
  75.  
  76. code_int free_ent = 0;            /* first unused entry */
  77. int exit_stat = 0;
  78.  
  79. code_int getcode();
  80.  
  81. Usage() {
  82. fprintf(stderr,"Usage: decomp infile outfile\n");
  83. }
  84.  
  85. int nomagic = 0;    /* Use a 3-byte magic number header, unless old file */
  86. int zcat_flg = 0;    /* Write output on stdout, suppress messages */
  87. int quiet = 1;        /* don't tell me about compression */
  88.  
  89. /*
  90.  * block compression parameters -- after all codes are used up,
  91.  * and compression rate changes, start over.
  92.  */
  93. int block_compress = BLOCK_MASK;
  94. int clear_flg = 0;
  95. long int ratio = 0;
  96. /*
  97.  * the next two codes should not be changed lightly, as they must not
  98.  * lie within the contiguous general code space.
  99.  */
  100. #define FIRST    257    /* first free entry */
  101. #define    CLEAR    256    /* table clear output code */
  102.  
  103. char ifname[100], ofname [100];
  104.  
  105. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  106.  
  107.  
  108. /*****************************************************************
  109.  * TAG( main )
  110.  *
  111.  * Algorithm from "A Technique for High Performance Data Compression",
  112.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  113.  *
  114.  * Algorithm:
  115.  *     Modified Lempel-Ziv method (LZW).  Basically finds common
  116.  * substrings and replaces them with a variable size code.  This is
  117.  * deterministic, and can be done on the fly.  Thus, the decompression
  118.  * procedure needs no input table, but tracks the way the table was built.
  119.  */
  120.  
  121. main( argc, argv )
  122. register int argc; char **argv;
  123. {
  124.     struct stat statbuf;
  125.  
  126.  
  127.     if (argc <  3) {Usage(); exit(1);}
  128.     strcpy (ifname , argv[1]);
  129.     strcpy (ofname , argv[2]);
  130.  
  131.     if(maxbits < INIT_BITS) maxbits = INIT_BITS;
  132.     if (maxbits > BITS) maxbits = BITS;
  133.     maxmaxcode = 1L << maxbits;
  134.  
  135.         /* Open input file */
  136.         if ((freopen(ifname, "rb", stdin)) == NULL) {
  137.             perror(ifname); exit(1);
  138.         }
  139.         stat(ifname, &statbuf);
  140.         fsize = statbuf.st_size;
  141.         /* Another Turbo C bug -- can return wrong file sizes*/
  142.         if (fsize < 0) fsize = 1000000;
  143.         /* Check the magic number */
  144.         if (nomagic == 0) {
  145.             if ((getchar() != (magic_header[0] & 0xFF))
  146.              || (getchar() != (magic_header[1] & 0xFF))) {
  147.             fprintf(stderr, "%s: not in compressed format\n",
  148.                 ifname);
  149.             exit(1);
  150.             }
  151.             maxbits = getchar();    /* set -b from file */
  152.             block_compress = maxbits & BLOCK_MASK;
  153.             maxbits &= BIT_MASK;
  154.             maxmaxcode = 1L << maxbits;
  155.             if(maxbits > BITS) {
  156.             fprintf(stderr,
  157.             "%s: compressed with %d bits, can only handle %d bits\n",
  158.             ifname, maxbits, BITS);
  159.             exit(1);
  160.             }
  161.         }
  162.         /* Check for overwrite of existing file */
  163.         if (stat(ofname, &statbuf) == 0) {
  164.             char response[2];
  165.             response[0] = 'n';
  166.             fprintf(stderr, "%s already exists;", ofname);
  167.             fprintf(stderr, " do you wish to overwrite %s (y or n)? ",
  168.             ofname);
  169.             fflush(stderr);
  170.             read(2, response, 2);
  171.             while (response[1] != '\n') {
  172.                 if (read(2, response+1, 1) < 0) {    /* Ack! */
  173.                 perror("stderr"); break;
  174.                 }
  175.             }
  176.             if (response[0] != 'y') {
  177.             fprintf(stderr, "\tnot overwritten\n");
  178.             exit(1);
  179.             }
  180.         }
  181.         if (freopen(ofname, "wb", stdout) == NULL) {
  182.             perror(ofname);
  183.             exit(1);
  184.         }
  185.  
  186.     hsize = min(HSIZE, fsize); /* cannot have more codes than file size */
  187.     htab = (char_type huge*)farcalloc(hsize, sizeof(char_type));
  188.     if (htab == NULL) {
  189.     fprintf(stderr,"Not enough memory\n");
  190.     fprintf(stderr,"Far heap size %lu hsize %u\n",farcoreleft(), hsize);
  191.     exit(1);
  192.     }
  193.     codetab = (unsigned short huge*)farcalloc(hsize, sizeof(unsigned short));
  194.     if(codetab == NULL) {
  195.     fprintf(stderr, "Not enough memory\n");
  196.     fprintf(stderr,"Far heap size %lu hsize %u\n",farcoreleft(), hsize);
  197.     exit(1);
  198.     }
  199.     de_stack = (char_type *)malloc(8000);
  200.  
  201.     decompress();
  202.     exit(0);
  203. }
  204.  
  205.  
  206. /*
  207.  * Decompress stdin to stdout.  This routine adapts to the codes in the
  208.  * file building the "string" table on-the-fly; requiring no table to
  209.  * be stored in the compressed file.  The tables used herein are shared
  210.  * with those of the compress() routine.  See the definitions above.
  211.  */
  212.  
  213. decompress() {
  214.     register char_type *stackp;
  215.     register code_int finchar;
  216.     register code_int code, oldcode, incode;
  217.  
  218.     /*
  219.      * As above, initialize the first 256 entries in the table.
  220.      */
  221.     maxcode = MAXCODE(n_bits = INIT_BITS);
  222.     for ( code = 255; code >= 0; code-- ) {
  223.     tab_prefixof(code) = 0;
  224.     tab_suffixof(code) = (char_type)code;
  225.     }
  226.     free_ent = ((block_compress) ? FIRST : 256 );
  227.  
  228.     finchar = oldcode = getcode();
  229.     if(oldcode == -1)    /* EOF already? */
  230.     return;            /* Get out of here */
  231.     putchar( (char)finchar );        /* first code must be 8 bits = char */
  232.     if(ferror(stdout))        /* Crash if can't write */
  233.     writeerr();
  234.     stackp = de_stack;
  235.  
  236.     while ( (code = getcode()) > -1 ) {
  237.  
  238.     if ( (code == CLEAR) && block_compress ) {
  239.         for ( code = 255; code >= 0; code-- )
  240.         tab_prefixof(code) = 0;
  241.         clear_flg = 1;
  242.         free_ent = FIRST - 1;
  243.         if ( (code = getcode ()) == -1 )    /* O, untimely death! */
  244.         break;
  245.     }
  246.     incode = code;
  247.     /*
  248.      * Special case for KwKwK string.
  249.      */
  250.     if ( code >= free_ent ) {
  251.             *stackp++ = finchar;
  252.         code = oldcode;
  253.     }
  254.  
  255.     /*
  256.      * Generate output characters in reverse order
  257.      */
  258. #ifdef SIGNED_COMPARE_SLOW
  259.     while ( ((unsigned long)code) >= ((unsigned long)256) ) {
  260. #else
  261.     while ( code >= 256 ) {
  262. #endif
  263.         *stackp++ = tab_suffixof(code);
  264.         code = tab_prefixof(code);
  265.     }
  266.     *stackp++ = finchar = tab_suffixof(code);
  267.  
  268.     /*
  269.      * And put them out in forward order
  270.      */
  271.     do
  272.         putchar ( *--stackp );
  273.     while ( stackp > de_stack );
  274.  
  275.     /*
  276.      * Generate the new entry.
  277.      */
  278.     if ( (code=free_ent) < maxmaxcode ) {
  279.         tab_prefixof(code) = (unsigned short)oldcode;
  280.         tab_suffixof(code) = finchar;
  281.         free_ent = code+1;
  282.     }
  283.     /*
  284.      * Remember previous code.
  285.      */
  286.     oldcode = incode;
  287.     }
  288.     fflush( stdout );
  289.     if(ferror(stdout))
  290.     writeerr();
  291. }
  292.  
  293. /*****************************************************************
  294.  * TAG( getcode )
  295.  *
  296.  * Read one code from the standard input.  If EOF, return -1.
  297.  * Inputs:
  298.  *     stdin
  299.  * Outputs:
  300.  *     code or -1 is returned.
  301.  */
  302.  
  303. code_int
  304. getcode() {
  305.     register code_int code;
  306.     static long int offset = 0, size = 0;
  307.     static char_type buf[BITS];
  308.     register int r_off, bits;
  309.     register char_type *bp = buf;
  310.  
  311.     if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {
  312.     /*
  313.      * If the next entry will be too big for the current code
  314.      * size, then we must increase the size.  This implies reading
  315.      * a new buffer full, too.
  316.      */
  317.     if ( free_ent > maxcode ) {
  318.         n_bits++;
  319.         if ( n_bits == maxbits )
  320.         maxcode = maxmaxcode;    /* won't get any bigger now */
  321.         else
  322.         maxcode = MAXCODE(n_bits);
  323.     }
  324.     if ( clear_flg > 0) {
  325.             maxcode = MAXCODE (n_bits = INIT_BITS);
  326.         clear_flg = 0;
  327.     }
  328.     size = fread( buf, 1, n_bits, stdin );
  329.     if ( size <= 0 )
  330.         return -1;            /* end of file */
  331.     offset = 0;
  332.     /* Round size down to integral number of codes */
  333.     size = (size << 3) - (n_bits - 1);
  334.     }
  335.     r_off = offset;
  336.     bits = n_bits;
  337.     /*
  338.      * Get to the first byte.
  339.      */
  340.     bp += (r_off >> 3);
  341.     r_off &= 7;
  342.     /* Get first part (low order bits) */
  343. #ifdef NO_UCHAR
  344.     code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
  345. #else
  346.     code = (*bp++ >> r_off);
  347. #endif /* NO_UCHAR */
  348.     bits -= (8 - r_off);
  349.     r_off = 8 - r_off;        /* now, offset into code word */
  350.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  351.     if ( bits >= 8 ) {
  352. #ifdef NO_UCHAR
  353.         code |= (*bp++ & 0xff) << r_off;
  354. #else
  355.         code |= *bp++ << r_off;
  356. #endif /* NO_UCHAR */
  357.         r_off += 8;
  358.         bits -= 8;
  359.     }
  360.     /* high order bits. */
  361.     code |= (*bp & rmask[bits]) << r_off;
  362.     offset += n_bits;
  363. /* Turbo C sign extends, so correct this bug (?) */
  364. #if BITS > 15
  365.     code &= 0xffff;
  366. #endif
  367.     return code;
  368. }
  369.  
  370. writeerr()
  371. {
  372.     perror ( ofname );
  373.     unlink ( ofname );
  374.     exit ( 1 );
  375. }
  376.